In this Towers of Hanoi graphic demonstration the computer moves the rings continuously on a standard terminal that has simple cursor controls. It moves the rings from one tower to another by the rule: Only one ring can be moved at a time and no ring can be put on top of a smaller ring. | | | =|= | | ==|== | | ===|=== | | ====|==== | | =====|===== | | --------------------------------- Starting display for 5 TOWERS This program was originally written by Peter Midnight and published in FORTH DIMENSIONS, Vol II, No. 2, page 32. This version was modified by Fred H. Olson to meet the FORTH-83 Standard with double number standard extension and environmental dependencies. Minimum requirements: (approx) 1) Dictionary space required: 1350 bytes 2) Data stack required: 4 TOWERS:60 bytes, 12 TOWERS:124 bytes 3) Return stack required: 44 bytes 4) Mass storage required: blocks 0 thru 15 for code and shadows 5) Operator's terminal must be capable of cursor controls. Source code is in blocks 2 to 7, the corresponding "shadow" screens which document the code are in blocks 10 to 15. After resolving the enviromental dependencies on block 2 the program can be loaded with " 2 LOAD " After loading the program it is executed with " n TOWERS" where n is the number of rings. ( Towers of Hanoi, by Peter Midnight ) FORTH DEFINITIONS DECIMAL : TASK ; ( Environmental dependencies) ( Definitions for Osborne I using F83 FORTH : ) ( : AT 27 EMIT 61 EMIT 32 + EMIT 32 + EMIT ; ) ( : DARK 26 EMIT ; ) ( : KEY? 0 2 BIOS 0= NOT ; ) ( bios system call ) 12 CONSTANT NMAX 61 CONSTANT COLOR ( = ) 32 CONSTANT BL VARIABLE (N) NMAX (N) ! : #RINGS (N) @ ; CREATE RING NMAX ALLOT ( array [1...n] of bytes ) VARIABLE #MOVES VARIABLE SCOREX VARIABLE SCOREY 3 LOAD 4 LOAD 5 LOAD 6 LOAD 7 LOAD ( Towers of Hanoi, continued ) : 4DUP ( n1 n2 n3 n4 --- n1 n2 n3 n4 n1 n2 n3 n4 ) 2OVER 2OVER ; : 3DUP ( n1 n2 n3 --- n1 n2 n3 n1 n2 n3 ) DUP 2OVER ROT ; : DELAY ( n --- ) 0 DO 60 0 DO 127 127 * DROP LOOP LOOP ; : HALFDISPLAY ( n1 n2 --- ) 0 DO DUP EMIT LOOP DROP ; : <DISPLAY> ( y char ring# --- ) 2DUP HALFDISPLAY ROT 3 < IF BL ELSE 124 ( | ) THEN EMIT HALFDISPLAY ; : DISPLAY ( ring# x y char --- ) SWAP >R ROT ROT OVER - R@ ( char ring# xleft y ) AT R> ( char ring# y ) ROT ROT <DISPLAY> ; : SCORE-AT ( --- ) SCOREX @ SCOREY @ AT ; : MAKEBASE ( --- ) 0 #RINGS 4 + AT #RINGS 6 * 3 + 0 DO 45 EMIT LOOP ; ( Towers of Hanoi, continued ) : PRESENCE ( tower ring#-1 --- flag ) RING + C@ = ; : X-POS ( tower --- X-coord ) #RINGS 2* 1+ * #RINGS + ; : Y-POS ( tower --- Y-coord ) 4 SWAP #RINGS 0 DO DUP I PRESENCE NOT IF SWAP 1+ SWAP THEN LOOP DROP ; : RAISE ( ring# source.tower destiny.tower --- ) DROP DUP X-POS SWAP Y-POS 2 SWAP DO 2DUP I BL DISPLAY 2DUP I 1- COLOR DISPLAY -1 +LOOP 2DROP ; : LOWER ( ring# source.tower destiny.tower --- ) ROT 2DUP RING + 1- C! SWAP DUP X-POS SWAP Y-POS 1+ 2 DO 2DUP I 1- BL DISPLAY 2DUP I COLOR DISPLAY LOOP 2DROP DROP ; ( Towers of Hanoi, continued ) : MOVELEFT ( ring# source.tower destiny.tower --- ) X-POS SWAP X-POS 1- DO DUP I 1+ 1 BL DISPLAY DUP I 1 COLOR DISPLAY -1 +LOOP DROP ; : MOVERIGHT ( ring# source.tower destiny.tower --- ) X-POS 1+ SWAP X-POS 1+ DO DUP I 1- 1 BL DISPLAY DUP I 1 COLOR DISPLAY LOOP DROP ; : TRAVERSE ( ring# source.tower destiny.tower --- ) 2DUP > IF MOVELEFT ELSE MOVERIGHT THEN ; : MOVE ( ring# source.tower destiny.tower othr.twr --- ) DROP 3DUP RAISE 3DUP TRAVERSE LOWER 1 #MOVES +! SCORE-AT #MOVES @ . KEY? IF CR ." ok" ABORT THEN ; : MAKETOWER ( tower --- ) X-POS 4 #RINGS + 3 DO DUP I AT 124 EMIT LOOP DROP ; ( Towers of Hanoi, continued ) : RING1? ( ring n1 n2 n3 - ring n1 n2 n3 f ) 3 PICK 1 = ; : RING-1:SRC>OTHR ( ring src dest othr - ring-1 'src' 'othr' 'dest') >R >R SWAP 1- SWAP R> R> SWAP ; : RING-1:OTHR>DEST ( ring src dest othr - ring-1 'othr' 'dest' 'src') >R >R SWAP 1- SWAP R> R> SWAP ROT ; VARIABLE 'MULTIMOV : RECURSE 'MULTIMOV @ EXECUTE ; : MULTIMOV ( ring# src.twr dest.twr othr.twr --- ) RING1? IF MOVE ELSE 4DUP RING-1:SRC>OTHR RECURSE 4DUP MOVE RING-1:OTHR>DEST RECURSE THEN ; ' MULTIMOV 'MULTIMOV ! ( Towers of Hanoi, continued ) : SETUP ( #ofrings --) DARK 1 MAX NMAX MIN (N) ! #RINGS 6 + SCOREY ! 1 X-POS 4 - DUP SCOREX ! 0 AT #RINGS . ." TOWERS" RING #RINGS 1 FILL 3 0 DO I MAKETOWER LOOP MAKEBASE 1 #RINGS DO I 1 0 LOWER -1 +LOOP SCORE-AT ; : TOWERS ( #ofrings --- ) SETUP #RINGS 0 1 2 BEGIN ( ring# src.twr dest.twr othr.twr ) #RINGS 0 DO 7 EMIT 25 DELAY LOOP 0 #MOVES ! SCORE-AT ." MOVES" 4DUP MULTIMOV ROT 0 ( forever) UNTIL ; Towers of Hanoi by Peter Midnight published in FORTH DIMENSIONS, Vol II, No. 2, page 32. Forth 83 version by Fred H. Olson WB0YQM 1221 Russell Ave N Minneapolis, MN 55411 (612) 588-9532 | | | =|= | | ==|== | | ===|=== | | ====|==== | | =====|===== | | ======|====== | | --------------------------------------- Starting display for 6 TOWERS The FORTH 83 Standard document is available from the Forth Interest Group, P.O.Box 1105, San Carlos,CA 94070 ($15). F83 is a very good public domain implementation of the Forth 83 Standard for CP/M-80,CP/M-86,CP/M-68K and MSDOS computers and the Macintosh. F83 is available on disk for $25 from No Visible Support Software, Box 1344, 2000 Center Steet, Berkeley, CA 94704. The standard and F83 are also available in Minnesota from MNFIG c/o Fred Olson (address above). The 3 towers are numbered 0, 1 and 2 from the left and are represented by a vertical line of '|' characters. The rings are numbered from 1 to 12 and are represented by this number of '=' characters on either side of the tower. === AT , DARK and KEY? are enviroment dependent words === AT moves the cursor to the column X row Y. x is in the range 0-79, y in the range 0-23 where 0,0 is upper left corner DARK clears the screen and moves the cursor to 0 0 These versions of AT and DARK should work for systems using Televideo compatible terminals. KEY? Returns a true flag if a key has been pressed otherwise a false flag is left. NOTE that if a key has been pressed its value can be gotten with KEY. COLOR & BL are constants for the ASCII '=' & blank. #RINGS leaves the number of rings as stored in (N) RING is an array where the byte at RING + n - 1 holds the number of the tower that ring n is currently on. #MOVES holds the current number of moves. SCOREX & SCOREY hold the cursor coordinates of the location to display the current # of moves 4DUP duplicates the top 4 items on the stack. 3DUP duplicates the top 3 items on the stack. DELAY delays n/100 seconds. HALFDISPLAY outputs one half of a ring n2 at the current cursor location. n1 is the char to output. DISPLAY displays ring at x,y with char which is either a blank to erase a ring or COLOR to redraw one. SCORE-AT moves the cursor to location where score is displayed. MAKEBASE displays the baseline for the towers. PRESENCE returns a true flag if ring is on tower. X-POS returns the x-coord of vertical part of tower. Y-POS returns the y-coord of the top ring of tower . RAISE displays ring rising from tower. LOWER lowers ring over tower and updates RING array. MOVELEFT moves one ring of specified size from above one tower to above another tower to the left. MOVERIGHT moves one ring of specified size from above one tower to above another tower to the right. TRAVERSE moves one ring of specified size from above one tower to above another by checking the direction and calling MOVELEFT or MOVERIGHT as required. MOVE raises the top ring of specified size from the source tower and moves it over and lowers over the destination tower. Then checks for keystroke, if key pressed, terminates routine. MAKETOWER displays the specified tower. RING1? returns true flag if a move of ring 1 has been requested.RING-1:SRC>OTHR configures the stack for the sub-problem of moving a ring one smaller out of the way. RING-1:OTHR>DEST configures the stack for the sub-problem of moving the smaller ring from its out of the way tower to the original destination. 'MULTIMOV is an execution variable used to implement recursion in MULTIMOV in a standard way. ( RECURSE is not 83 Standard) MULTIMOV does all the work-- moves the rings from source tower to destination tower. Note that there is no loop structure in MULTIMOV. Instead MULTIMOV calls itself repeatedly via RECURSE. Each time MULTIMOV calls itself 4, additional stack items are needed. ( see '4DUPs' ) Note that MOVE uses the same four stack items. Init execution variable SETUP displays the towers initially and inits the array RING. n TOWERS initiates the whole display which continues til key is pressed, see MOVE for termination. | | | =|= | | ==|== | | ===|=== | | ====|==== | | =====|===== | | ======|====== | | =======|======= | | ---------------------------------------------- Starting display for 7 TOWERS
